public class Solution397 {

    int minStep = Integer.MAX_VALUE;

    void travel(long n, int tmpStep){
        if(tmpStep >= minStep){
            return;
        }
        if(n == 1){
            minStep = tmpStep;
            return;
        }
        if((n & 1) == 1){
            travel(n - 1, tmpStep + 1);
            travel(n + 1, tmpStep + 1);
        }
        else{
            travel(n >> 1, tmpStep + 1);
        }
    }

    public int integerReplacement(int n) {
        travel(n, 0);
        return minStep;
    }

    public static void main(String[] args) {
        Solution397 s = new Solution397();
        s.integerReplacement(2147483647);
    }
}
